package org.example.myleet.p827;

import java.util.*;

public class Solution {

    private static final int[][] DIRECTIONS = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    static class Land {
        int[] topLeft;
        Set<String> border;
        int area;

        public Land(int[] topLeft, Set<String> border, int area) {
            this.topLeft = topLeft;
            this.border = border;
            this.area = area;
        }
    }

    public int largestIsland(int[][] grid) {
        List<Land> landList = new ArrayList<>();
        int n = grid.length;
        //BFS找到每一块岛屿的边界及其面积
        boolean[][] visited = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    int[] topLeft = new int[]{i, j};
                    Set<String> border = new HashSet<>();
                    Queue<int[]> queue = new LinkedList<>();
                    queue.add(topLeft);
                    visited[i][j] = true;
                    int area = 1;
                    while (!queue.isEmpty()) {
                        int size = queue.size();
                        while (size > 0) {
                            int[] p = queue.poll();
                            for (int k = 0; k < 4; ++k) {
                                int i_ = p[0] + DIRECTIONS[k][0];
                                int j_ = p[1] + DIRECTIONS[k][1];
                                if (0 <= i_ && i_ < n && 0 <= j_ && j_ < n && !visited[i_][j_]) {
                                    if (grid[i_][j_] == 1) {
                                        queue.add(new int[]{i_, j_});
                                        visited[i_][j_] = true;
                                        ++area;
                                    } else {
                                        border.add(i_ + "_" + j_);
                                    }
                                }
                            }
                            --size;
                        }
                    }
                    landList.add(new Land(topLeft, border, area));
                }
            }
        }
        int maxLandArea = 1;
        if (landList.size() > 0) {
            maxLandArea = Math.max(maxLandArea, landList.get(0).area);
        }
        //将每个边界点涉及到的岛屿用map聚合在一起
        Map<String, Integer> borderMapArea = new HashMap<>();
        for (Land land : landList) {
            for (String border : land.border) {
                Integer area = borderMapArea.getOrDefault(border, 1);
                area += land.area;
                borderMapArea.put(border, area);
                maxLandArea = Math.max(maxLandArea, area);
            }
        }
        //如果整个grid就是一块陆地，最大面积是n * n
        maxLandArea = Math.min(maxLandArea, n * n);
        return maxLandArea;
    }
}
